package me.shan.search;

import org.junit.Assert;

/**
 * 描述：求局部最小值
 * 二分法
 *
 * @author liuchuang
 * @date 2021/6/14
 */
public class LocalMinimum {

    /**
     * 求局部最小值，数组限定，相邻数据不相等
     * 数组长度大余等于3
     * @param array 入参数组
     * @return 是否局部最小的下标
     */
    public static int search(int[] array) {
        int left = 0, right = array.length - 1;
        if (array[left] < array[left+1]) {
            return 0;
        }
        if (array[right] < array[right - 1]) {
            return right;
        }
        int mid;
        while (left < right) {
            mid = left + ((right - left) >> 1);
            if (array[mid] < array[mid + 1] && array[mid] < array[mid - 1]) {
                return mid;
            } else if (array[mid] > array[mid - 1]) {
                right = mid - 1;
                if (array[right] < array[right - 1]) {
                    return right;
                }
            } else {
                left = mid + 1;
                if (array[left] < array[left+1]) {
                    return 0;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {10, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        Assert.assertEquals(1, search(array));
    }

}
